In formal language theory, the Chomsky–Schützenberger theorem is a statement about the number of words of a given length generated by an unambiguous context-free grammar. The theorem provides an unexpected link between the theory of formal languages and abstract algebra. It is named after Noam Chomsky and Marcel-Paul Schützenberger.
In order to state the theorem, we need a few notions from algebra and formal language theory.
A power series over is an infinite series of the form
with coefficients in . The multiplication of two formal power series and is defined in the expected way as the convolution of the sequences and :
In particular, we write , , and so on. In analogy to algebraic numbers, a power series is called algebraic over , if there exists a finite set of polynomials each with rational coefficients such that
Having established the necessary notions, the theorem is stated as follows.
Proofs of this theorem are given by Kuich & Salomaa (1985), and by Panholzer (2005).